// 139.单词拆分
package LeetcodeHot100;

import java.util.List;

public class Solution139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];

        for (int i = 1; i < s.length() + 1; i++) {
            if (wordDict.contains(s.substring(0, i)))
                dp[i] = true;
            else {
                for (int j = 0; j < i; j++) {
                    if (dp[j] == true && wordDict.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[s.length()];
    }
}
